package com.zbcn.algorithm;

/**
 * 求给定数组的逆序度
 * 如何用编程的方法求解出一组数据的有序对个数或者逆序对个数
 */
public class T23_nixudu {

    /**
     * 全局变量-逆序度
     */
    private int num = 0;


    private int count(int[] a,int n){
        num = 0;
        mergeSortCount(a,0,n-1);
        return num;
    }

    private void mergeSortCount(int[] a, int p, int r){
        if (p >= r){
            return;
        }
        int q = (r + p)/2;
        mergeSortCount(a,p,q);
        mergeSortCount(a, q +1,r);
        merge(a,p,q,r);
    }

    //在每次合并操作过程中，我们顺便计算两个小数组之间的逆序对个数，把这些计算出来的逆序对个数求和，
    //就是整个逆序对个数
    public void merge(int[] a, int p,int q,int r){

        int i = p, j = q+1, k = 0;

        // 临时数组，存储排好序的数据
        int[] temp = new int[r-p + 1];

        while (r <=q && j <=r){
            if (a[i] < a[j]){
                //顺序
                temp[k++] = a[i++];
            }else {
                // 统计 p -q 之间，比 a[j] 元素大的个数
                num = (q-i +1);
                temp[k++] = a[j++];
            }
        }

        //处理剩下的
        while (i <=q){
            temp[k++] = a[i++];
        }
        //处理剩下的
        while (j <=r){
            temp[k++] = a[j++];
        }
        // 从temp 复制回 a
        for ( i = 0; i <r-p; ++i){
            a[p+i] = temp[i];
        }
    }
}
